/*
 * @lc app=leetcode.cn id=101 lang=cpp
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
 public:
  /*递归的方式
    bool isSymmetric(TreeNode* root)
    {
        if(!root) return true; // 如果是空树，对称
        return dfs(root->left, root->right); // 进入镜像二叉树的搜索
    }

    bool dfs(TreeNode* p, TreeNode* q)
    {
        if(!p || !q) return !p && !q; // 如果左树和右树都为空，才返回ture
        return p->val==q->val && dfs(p->left, q->right) && dfs(p->right,q->left); // 这个是递推方程
    }*/

  bool isSymmetric(TreeNode* root)
  {
    if (!root) return true;
    stack<TreeNode*> left, right;
    TreeNode *l = root->left, *r = root->right;
    while (l || r || left.size() || right.size())
    {
      // 遍历
      while (l && r)
      {
        // 左入栈，再左
        left.push(l), l = l->left;
        // 右入栈，再右
        right.push(r), r = r->right;
      }
      // 这个地方没看懂
      if (l || r) return false;  // l和r一个为空，一个不为空，返回false, 都存在不会返回

      l = left.top(), left.pop();
      r = right.top(), right.pop();
      if (l->val != r->val) return false;

      l = l->right, r = r->left;
    }

    return true;
  }
};
// @lc code=end
